import java.util.Random;

public class QuickSort {

    public static void main(String[] args) {
        int[] nums = {10,9,8,7,6,5,4,3,2,1};
        quickSort(nums,0,nums.length-1);
        System.out.println();
    }

    public static void quickSort(int[] nums,int start,int end) {
        if(start>=end) return;
        //1.选基准元素，可以选第一个
        int patition = nums[new Random().nextInt(end-start+1)+start];
        //2.根据基准元素划分数组
        int left = start - 1;
        int right = end + 1;
        int i = start;
        while(i<right) {
            if(nums[i]<patition) swap(nums,++left,i++);
            else if(nums[i]>patition) swap(nums,--right,i);
            else i++;
        }
        //3.继续递归子模块[start,left][left+1,i][right,end]
        quickSort(nums,start,left);
        quickSort(nums,right,end);
    }

    public static void swap(int[] nums,int i,int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }





}
